#include <algorithm>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

// auto inc init val
int work_id_inc = 1;

// 时间片
int timelen = 8;

// simple_turn_timer timer
int simple_turn_timer = 0;
int simple_turn_count = 0;

// define program
struct Work {
  int id, ht, ts;           //进程id, 优先级, 到达时间 timeslicen
  int st, ed;               // start time, end time
  int cpuw, iow, cput, iot; // cpu wait io wait cput cost io cost
  int cpust, cpued, iost, ioed;
  bool in_wait, is_ok, working; // progress status
  bool is_first_cpu; // 标记是否是第一次cpu执行， 统计cpu开始执行时间
  int page_access_times, page_lack_of,
      page_lack_percent; // 页面访问次数,  页面缺页次数，页面缺页率
  vector<int> jobs;      // 页面访问序列
  int sgp;               // segment point
  friend ostream &operator<<(ostream &out, const Work &w) {
    out << w.id << " " << w.ht << " " << (w.jobs).size() << " ";
    for (auto x : w.jobs) {
      out << x << " ";
    }
    out << endl;
    return out;
  }
  bool operator<(const Work &w) const { return ht < w.ht; }
  bool operator==(Work *w) const { return id < w->id; }
};

// cpu, io queue
vector<Work *> qwait;
// queue<Work> qok;

// cpu
bool cpu;
void datacreate(int n) {
  if (n > 10) {
    cout << "进程数量不能大于10" << endl;
    exit(1);
  }
  fstream f("job", ios::out);
  vector<Work> jobs;
  f << n << endl;
  for (int i = 0; i < n; i++) {
    Work w = {
        .id = work_id_inc++,
        .ht = rand() % 1000,
    };
    int j = rand() % 31 + 20;
    for (int k = 0; k < j; k++) {
      (w.jobs).push_back(rand() % 11 + 10);
    }
    jobs.push_back(w);
  }
  sort(jobs.begin(), jobs.end());
  for (auto x : jobs) {
    f << x;
  }
  f.close();
}

void init(int n) { datacreate(n); }

// [x] 假定缺页中断，耗费单位时间忽略不计算。

// 处理页面访问
vector<unordered_map<int, int>> *pagecache =
    new vector<unordered_map<int, int>>(11);
/* @param pageno 访问逻辑页号 */
void fifo(Work *const cpuworkingWork, const int no, const int pageno,
          const int physize) {
  unordered_map<int, int> &m = (*pagecache)[no];
  if (m[pageno] == 0) {

    cpuworkingWork->page_lack_of++;
    cout << cpuworkingWork->id << " 号进程发生缺页中断"
         << "当前缺页次数 " << cpuworkingWork->page_lack_of << endl;
    m[pageno] = 1;
    if (m.size() > physize) {
      pair<int, int> tmp = {0, 0};
      for (auto &x : m) {
        cout << "fi " << x.first << " se " << x.second;
      }
      for (auto &x : m) {
        if (tmp.second < x.second) {
          tmp = x;
        }
      }
      cout << endl << "被删除的元素是" << tmp.first << endl;
      m.erase(tmp.first);
      // m[pageno] = page_counter[no]--;
    }
  } else {
    for (auto &x : m) {
      x.second++;
    }
  }

  vector<pair<int, int>> res;
  for (auto x : m) {
    res.push_back(x);
  };
  sort(res.begin(), res.end(),
       [](auto &left, auto &right) { return left.second > right.second; });
  for (auto &x : res) {
    cout << x.first << " ";
  }
  cout << endl;
}
void lru(Work *const cpuworkingWork, const int no, const int pageno,
         const int physize) {
  unordered_map<int, int> &m = (*pagecache)[no];
  if (m[pageno] != 0) {
    for (auto &x : m) {
      if (pageno != x.first) {
        x.second++;
      }
    }
    m[pageno] = 1;
  } else {
    // 发生缺页中断
    cout << cpuworkingWork->id << " 号进程发生缺页中断"
         << "当前缺页次数 " << cpuworkingWork->page_lack_of << endl;
    cpuworkingWork->page_lack_of++;
    m[pageno] = 1;
    if (m.size() > physize) {
      pair<int, int> tmp = {0, 0};
      for (auto &x : m) {
        if (tmp.second < x.second) {
          tmp = x;
        };
        cout << "fi " << x.first << " se " << x.second;
      }
      cout << endl << "被删除的元素是" << tmp.first << endl;
      m.erase(tmp.first);
    }
  }
  vector<pair<int, int>> res;
  for (auto x : m) {
    res.push_back(x);
  };
  sort(res.begin(), res.end(),
       [](auto &left, auto &right) { return left.second < right.second; });
  for (auto &x : res) {
    cout << x.first << " ";
  }
  cout << endl;
}
void handle_page_req(Work *const cpuworkingWork, const int no, const int pageno,
                     const int physize, int type) {
  switch (type) {
  case 1: {
    fifo(cpuworkingWork, no, pageno, physize);
    break;
  }
  case 2: {
    lru(cpuworkingWork, no, pageno, physize);
    break;
  }
  default: {
    lru(cpuworkingWork, no, pageno, physize);
    break;
  }
  }
}
void test_page_handler(Work *const cpuworkingWork) {
  vector<int> res = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};
  for (auto &x : res) {
    handle_page_req(cpuworkingWork, 1, x, 4, 2);
  }
}

void test_page_handler2(Work *const cpuworkingWork) {
  vector<int> res = {2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2};
  for (auto &x : res) {
    handle_page_req(cpuworkingWork, 1, x, 4, 1);
  }
}
// 读取数据
vector<Work *> jobs;
void input() {
  fstream r("job", ios::in);
  int n;
  r >> n;

  while (n--) {
    Work *t = new Work{};
    int jobszie;
    r >> t->id >> t->ht >> jobszie;
    while (jobszie--) {
      int a;
      r >> a;
      t->jobs.push_back(a);
    }
    jobs.push_back(t);
  }
}

// 简单时间片流转
void simple_turn(const int physize, const int type) {
  // for (auto x:jobs){ cout << *x; }
  Work *cpuworkingWork = nullptr;
  bool cpu = false;
  bool complete = false;
  for (int i = 0; i < 9990; i++) {
    if (cpu && cpuworkingWork != nullptr) {
      Work *t = cpuworkingWork;
      cout << "当前时间是 " << simple_turn_count << " " << cpuworkingWork->id
           << " 号进程"
           << "正在处理序列 " << t->sgp << " 序列号 "
           << cpuworkingWork->jobs[t->sgp] << "还剩下 "
           << t->jobs.size() - t->sgp - 1 << endl;
      handle_page_req(cpuworkingWork, t->id, t->jobs[t->sgp++], physize, type);
      if (t->sgp >= t->jobs.size()) {
        cout << "当前时间是 " << simple_turn_count << " " << cpuworkingWork->id
             << " 号进程完成" << endl;
        complete = true;
        qwait.erase(find(qwait.begin(), qwait.end(), t));
        cpuworkingWork->working = false;
        cpuworkingWork = nullptr;
        cpu = false;
      }
    }
    simple_turn_timer++;
    simple_turn_count++;
    if (complete || simple_turn_timer % timelen == 0) {
      simple_turn_timer = 0;
      for (auto x : jobs) {
        if (x->in_wait)
          continue;
        if (simple_turn_count > x->ht) {
          cout << x->id << " 号进程加入qwait ";
          for (auto x : qwait) {
            cout << x->id << " working " << x->working << " ";
          };
          cout << endl;
          qwait.push_back(x);
          x->in_wait = true;
        }
      }
      if (cpu && cpuworkingWork != nullptr) {
        cout << cpuworkingWork->id << "号进程"
             << " cpu 锁释放";
        cpuworkingWork->working = false;
        qwait.erase(find(qwait.begin(), qwait.end(), cpuworkingWork));
        qwait.push_back(cpuworkingWork);
        cout << "qwait 状态";
        for (auto x : qwait) {
          cout << x->id << " working " << x->working << " ";
        };
        cout << endl;
        cpu = false;
      }
      if (!cpu) {
        for (auto x : qwait) {
          if (cpu)
            continue;
          if (x->working)
            continue;
          cout << x->id << "号进程开始工作 " << endl;
          cpuworkingWork = x;
          cpu = true;
        }
      }
    }
  }
}

int main(int argc, char *argv[]) {
  // init(10);
  input();
  if (argc < 3) {
    exit(1);
  }
  // 测试页面调度
  // test_page_handler(); pass
  // test_page_handler2();
  const int PHYSIZE = stoi(argv[1]);
  enum DISK_HANDLE { FIFO = 1, LRU = 2 };
  int type = stoi(argv[2]);
  simple_turn(PHYSIZE, type);
  string type_str = type == DISK_HANDLE::FIFO ? "fifo" : "lru";
  fstream f("result-" + type_str + "-" + to_string(PHYSIZE), ios::out);
  // 输出结果
  // f << "进程号 \t" << "缺页率\t" << endl;
  int n = jobs.size();
  f << n << " " << PHYSIZE << endl;
  int pga_sum = 0, pgl_sum = 0;
  double pgf_sum = 0;
  for (auto x : jobs) {
    double pgf = double(x->page_lack_of) / double(x->jobs.size());
    int pga = x->jobs.size() - x->page_lack_of;
    pgf_sum += pgf;
    pga_sum += pga;
    pgl_sum += x->page_lack_of;
    f << x->id << " " << x->ht << " " << x->ed << " "
      << x->jobs.size() - x->page_lack_of << " "
      << double(x->page_lack_of) / double(x->jobs.size()) << endl;
  }
  f << pga_sum / n << " " << pgl_sum / n << " " << pgf_sum / n << endl;

  return 0;
}
